#define _CRT_SECURE_NO_WARNINGS 1
#include<set>
#include<map>
#include<queue>
#include<iostream>
using namespace std;

//虚函数
struct countVal
{
	bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)
	{
		return l->second < r->second;
	}
};

void set_test()
{
	multiset<int> s;
	s.insert(3);
	s.insert(3);
	s.insert(3);
	s.insert(3);
	s.insert(3);
	s.insert(3);
	s.insert(2);
	s.insert(5);
	s.insert(6);
	s.insert(1);
	s.insert(8);
	auto pos = s.find(3);
	while (pos != s.end() && *pos == 3)
	{
		s.erase(pos++);
	}
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

}

void map_test1()
{
	multimap<string,int> m;
	pair<string, int> kv1("apple", 1);
	m.insert(kv1);
	m.insert(make_pair("apple", 1));
	m.insert(make_pair("apple", 1));
	m.insert(make_pair("apple", 1));
	m.insert(make_pair("apple", 1));
	cout << m.count("apple");
	/*auto it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		it++;
	}*/
}

void map_test2()
{
	map<string, int> countMap;
	string arr[] = { "苹果","苹果" ,"苹果" ,"苹果" ,"樱桃" ,"西瓜","杨桃","樱桃" ,"樱桃" ,"苹果","西瓜" };
	/*for (auto& str : arr)
	{
		const auto& kv = countMap.insert(make_pair(str, 1));
		if(kv.second == false)
			++(kv.first->second);
	}*/
	for (const auto& cm : arr)
	{
		++countMap[cm];
	}
	////第一种方法：用multimap反着存一次，再用迭代器迭代输出
	//multimap<int, string,greater<int>> count;
	//for (auto& kv : countMap)
	//{
	//	count.insert(make_pair(kv.second, kv.first));
	//}
	//auto it = count.begin();
	//while (it != count.end())
	//{
	//	cout << it->second << endl;
	//	++it;
	//}

	//第二种方法，用vector存地址（节省空间），再用sort排序（写一个虚函数定义排序比较方法）//比较麻烦但是省空间
	//第三种方法用优先级队列,用vector存迭代器，写一个虚函数比较
	priority_queue<map<string,int>::iterator,vector<map<string, int>::iterator>,countVal> pq;
	auto it = countMap.begin();
	while (it != countMap.end())
	{
		pq.push(it);
		it++;
	}
	int k = 3;
	while (k--)
	{
		cout << pq.top()->first << ":" << pq.top()->second << endl;
		pq.pop();
	}
}

int main()
{
	//set_test();
	//map_test1();
	map_test2();
	return 0;
}